package src.java.medium;

public class Solution55 {
    public static int findMaxLen(int[] nums, int start, int end) {
        int maxLen = 0;
        for (int i = start; i <= end; i++) {
            if (nums[i] + i > maxLen) {
                maxLen = nums[i] + i;
            }
        }
        return maxLen;
    }

    public static boolean canJump(int[] nums) {
        if (nums[0] >= nums.length - 1) return true;
        int start = 1;
        int end = findMaxLen(nums, 0, 0);
        for (int i = 1; i < nums.length; i++) {
            int temp = end;
            end = findMaxLen(nums, start, end);
            if (end >= nums.length - 1) return true;
            start = temp;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 0, 4};
        canJump(nums);
    }
}
